https://www.acmicpc.net/problem/4195

친구 네트워크에 몇 명이 있는지 구하는 문제

합집합(union-find) 찾기 알고리즘

부모 테이블과 자식 테이블로 나뉘는데 자식이 본인이고 부모가 가리키고 있는 값임

def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        parent[y] = x
        # 친구 그룹이 합쳐질 때 친구가 가지고 있는 친구 수 더해줌
        number[x] += number[y]

test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()

    f = int(input())

    for _ in range(f):
        x, y = input().split()

        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = x
            number[y] = 1

        union(x, y)

        print(number[find(x)])